The present invention relates to integrated circuit memory devices and, more particularly, to content addressable memory (CAM) devices and methods of operating same.
In many memory devices, including random access memory (RAM) devices, data is typically accessed by supplying an address to an array of memory cells and then reading data from the memory cells that reside at the supplied address. However, in content addressable memory (CAM) devices, data within a CAM array is not accessed by initially supplying an address, but rather by initially applying data to the array and then performing a compare operation to identify one or more locations within the array that contain data equivalent to the applied data and thereby represent a xe2x80x9cmatchxe2x80x9d condition. In this manner, data is accessed according to its content rather than its address. Upon completion of the compare operation, the identified location(s) containing equivalent data is typically encoded to provide an address at which the equivalent data is located. If multiple locations are identified in response to the compare operation, then priority encoding operations may be performed to identify a best or highest priority match. Such priority encoding operations frequently utilize the physical locations of multiple matches within the CAM array to identify a highest priority match. Exemplary CAM cells and CAM memory devices are more fully described in U.S. Pat. Nos. 5,706,224, 5,852,569 and 5,964,857 to Srinivasan et al. and U.S. Pat. Nos. 6,101,116, 6,256,216 and 6,128,207 to Lien et al., assigned to the present assignee, the disclosures of which are hereby incorporated herein by reference.
CAM cells are frequently configured as binary CAM cells that store only data bits (as xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d logic values) or as ternary CAM cells that store data bits and mask bits. As will be understood by those skilled in the art, when a mask bit within a ternary CAM cell is inactive (e.g., set to a logic 0 value), the ternary CAM cell may operate as a conventional binary CAM cell storing an xe2x80x9cunmaskedxe2x80x9d data bit. When the mask bit is active (e.g., set to a logic 1 value), the ternary CAM cell is treated as storing a xe2x80x9cdon""t carexe2x80x9d (X) value, which means that all compare operations performed on the actively masked ternary CAM cell will result in a cell match condition regardless of the value of the applied data bit versus the stored data bit. Thus, if a logic 0 data bit is applied to a ternary CAM cell storing an active mask bit and a logic 1 data bit, the compare operation will indicate a cell match condition. A cell match condition will also be indicated if a logic 1 data bit is applied to a ternary CAM cell storing an active mask bit and a logic 0 data bit. Accordingly, if a data word of length N, where N is an integer, is applied to a ternary CAM array having a plurality of entries therein of width N, then a compare operation will yield one or more entry match conditions whenever all the unmasked data bits of a word stored in the ternary CAM array are identical to the corresponding data bits of the applied word. This means that if the applied data word equals {1011}, the following stored words will result in an entry match condition in a CAM comprising ternary CAM cells (i.e., a ternary CAM): {1011}, {X011}, {1X11}, {10X1}, {101X}, {XX11}, {1XX1}, . . . , {1XXX}, {XXXX}.
Applications using CAMs include database management, disk caching, pattern and image recognition and artificial intelligence. CAMs are also well suited for use in routing network traffic, such as in network address lookup or packet switching. For example, FIG. 1 illustrates a simplified view of a network switch 100. The network switch 100 may communicate with a network through a plurality of network ports, shown as ports zero (0) through seven (7). The switch 100 may receive network traffic on one port and determine to which of its other ports that traffic should be routed. As will be understood by those skilled in the art, the network traffic may include a packet stream of data containing a leading destination address. The network switch 100 may select a leading portion of the packet stream and provide it to a ternary CAM 102. The CAM 102 may contain entries that include predetermined routing information, with the CAM address of each of these entries designating a port of the network switch 100. When the portion of the packet stream is applied as data to the CAM 102 during a compare operation, the CAM 102 may return a CAM address. This CAM address may correspond to the location of an entry within the CAM 102 that matches the applied portion of the packet stream. This returned CAM address may then be used by the network switch 100 to direct the packet stream to a desired port that will enable the packet stream to reach its destination address.
Referring now to FIG. 2, a conventional network routing application may also utilize a switch controller 200 that receives network packets from an external source and routes the network packets through a switch 206. The switch controller 200 may provide a portion of a destination address within a packet to an accompanying CAM 202. In response, the CAM 202 may perform a compare operation and generate an address of a matching entry. This generated address may be used as a pointer to acquire network address translation information or other routing information contained within a RAM 204. The information provided by the RAM is then conveyed to the controller 200 for use in routing the packet through the switch 206. In this manner, a CAM 202 may be used to provide a mechanism for locating address translation and routing information for network packet addresses.
In the event multiple matches (i.e., multiple matching entries) are detected during a compare operation, conventional physical priority encoding techniques may be utilized to identify a best or highest priority match (i.e., a highest priority matching entry) that should be used to perform the routing of the packet stream in a preferred manner. This highest priority match is frequently referred to as a longest prefix match (LPM), where the prefix may be defined as a first portion of a network packet address. A conventional technique for identifying an LPM will now be described with reference to the entries illustrated within the CAM 102 of FIG. 1. If the destination address within the packet stream is a bit sequence equal to {01100010}, then a compare operation within the CAM 102 of FIG. 1 will result in three (3) matches. These three matches correspond to the entries at address 0, designating port 0, address 3, designating port 3, and address 6, designating port 6. As illustrated by the entries within the CAM 102, the match corresponding to the entry at address 0 may be treated as the highest priority match because it is the entry with the largest number of unmasked data bits that are equivalent to the applied destination address. The detection of this highest priority match can be relatively simple if the entries within the CAM 102 are presorted according to priority or are arranged within sectors, with each sector containing entries having the same number of unmasked bits and being physically arranged according to priority. As described herein, sectors within a CAM may have the same or different number of entries therein.
As illustrated by FIG. 1, entries having no masked bits may be stored in a first sector (illustrated as spanning addresses 0-2 within the CAM 102) and entries having only one (1) masked bit may be stored in a second sector (illustrated as spanning only address 3 within the CAM 102). Entries having a greater number of masked bits are also stored in respective lower priority sectors within the CAM 102. By intentionally arranging all entries having the same number of masked bits within the same sector and by physically locating the sectors in order of their priority within the CAM 102, a simple physical encoding technique may be used to identify the highest priority match as the match having the highest number of unmasked bits relative to the other matches. This technique typically includes selecting the match that is in the highest relative priority sector in the event matches within multiple sectors are present. If multiple matches are present within the same highest relative priority sector, then any of the equivalent matches may be selected as the xe2x80x9cbestxe2x80x9d match.
U.S. Pat. No. 6,237,061 to Srinivasan et al., entitled xe2x80x9cMethod For Longest Prefix Matching in a Content Addressable Memory,xe2x80x9d discloses a similar arrangement of locally masked entries that need not be stored in equivalently sized sectors or blocks within a CAM, but nonetheless are stored by loading a plurality of Class-less Inter-Domain Routing (CIDR) addresses into respective ones of a plurality of CAM entries in a predetermined order such that increasing numerical CAM entry addresses correspond to CIDR addresses having decreasing prefix values (i.e., a greater number of actively masked bits). If a compare operation is then performed and a matching entry within the preordered CAM is present, a suitable match flag signal is asserted, and the index of the matching CAM entry (as well as any associated routing data stored in the CAM or in an external memory such as an SRAM array) is provided as an output. Alternatively, if there are multiple matching entries in the CAM, a suitable multiple match flag signal is asserted and, in response thereto, an associated priority encoder that is coupled to the CAM outputs the highest priority location. This highest priority location corresponds to the CAM entry having the lowest index, which by definition is the longest prefix matching entry.
Partitioning a CAM into a plurality of prioritized sectors may limit the flexibility of the CAM because the content of the CAM may need to be presorted into appropriate sectors according to mask length. Because the sectors are frequently partitioned into arrays of equal size to accommodate a variety of different applications, and because the number of entries required in each sector may be constantly changing during operation, it may not be possible to partition a CAM into fixed sized sectors that do not result in a significant number of unused entry locations. For example, if a CAM is divided into 16 equal sectors in order to support entries having as many as 15 actively masked bits and each sector is the same size, then much of the CAM may go unused if many of the sectors are only partially filled with entries of a respective mask length. Furthermore, it may not be practical to divide a CAM array into more than a relatively small number M of equally sized sectors because the size of each sector scales as 1/M, some applications may require a large number of priority levels (i.e., large M) and the number of entries at a given priority level may exceed H/M, where H is the height of the CAM (e.g., total number of rows in the CAM array). Finally, even if the CAM is not arranged into equivalently sized sectors, the loading of entries into the CAM in a predetermined order, such that increasing (or decreasing) CAM entry addresses correspond to entries having decreasing (or increasing) prefix values, may require time consuming operations to reload the CAM be performed when new entries having different prefix values are added to the CAM.
Thus, notwithstanding the relative simplicity of determining highest priority matches using conventional physical priority encoding techniques, additional techniques are needed that do not require presorting of entries and do not result in significant amounts of unused CAM space.
Content addressable memory (CAM) devices according to a first embodiment of the present invention include CAM arrays that can identify a best match(es) from a plurality of matches when an operation to compare data applied to a CAM array against data entries within the CAM array is performed. This best match identification operation is preferably performed internal to the CAM array. The best match identification operation does not require operations to determine a highest priority match based on the relative physical locations of multiple matching entries that might be identified within the CAM array during a compare operation. Accordingly, a CAM device that incorporates the first embodiment of the present invention may not require that the CAM array(s) therein be sectored into groups of entry locations (e.g., rows) having ordered priorities or that each CAM array within a multi-array CAM device be treated as a respective sector. Nonetheless, the entries within the CAM array that contain at least one actively masked bit preferably meet a masked bit location (MBL) constraint. This constraint requires that for every individual entry in a CAM array having at least one actively masked bit, all other entries in the same searchable CAM array having the same or fewer number of actively masked bits have each of their actively masked bit(s) in a respective location that overlaps a location of an actively masked bit in the individual entry.
A preferred CAM device may include an array of memory cells arranged as a plurality of rows of memory cells and a plurality of columns of memory cells that are electrically coupled to a respective plurality of data lines. Preferably integrated within the memory cell array is a data comparison circuit that identifies a longest prefix match (LPM) between data bits applied to the data lines and data bits (along with mask bits) that are randomly stored on a row basis in the plurality of rows of memory cells. CAM entries need not be grouped according to priority within respective sectors. The data comparison circuit preferably includes a plurality of comparison units that are associated with corresponding memory cells in the memory cell array, with each comparison unit and corresponding memory cell collectively forming a respective novel CAM cell in a CAM array.
The data comparison circuit may identify a longest prefix match in two phases during a single compare operation by identifying a first plurality of matches between the applied data bits and data bits stored with or without active mask bits as entries within the CAM array and then eliminating one or more of the first plurality of matches that do not represent a longest prefix match. This elimination phase of the compare operation may be performed in-sync with a leading edge of a delayed enable signal that may be asserted a predetermined amount of time after new data is applied to the CAM array. This operation to eliminate one or more of the first plurality of matches may include blocking at least one CAM cell associated with an identified match from indicating a cell match condition. According to a preferred aspect of this embodiment, the data comparison circuit identifies a longest prefix match by blocking at least one actively masked CAM cell, in an entry having all unmasked data bits that are equivalent to corresponding data bits applied to the data lines (i.e., a matching entry), from indicating a cell match condition. In particular, the data comparison circuit may force the actively masked CAM cell associated with a matching entry to indicate a cell miss during a compare operation, irrespective of whether the CAM cell is actually storing a matching data bit. According to another aspect of this embodiment, the data comparison circuit is not responsive to a delayed enable signal and the compare operation is not performed in two distinct phases.
According to another embodiment of the present invention, a CAM device includes a CAM array having circuitry therein that preferably identifies a best match between data applied to the CAM array and data entries within the CAM array. This identification operation is performed by blocking at least one actively masked CAM cell in a row within the CAM array from indicating a cell match condition during a compare operation, even when all other unmasked CAM cells in the same row are indicating cell matches with the applied data. This operation to block the at least one actively masked CAM cell preferably includes causing the at least one actively masked CAM cell to indicate a cell miss even when a data bit within the at least one actively masked CAM cell matches the corresponding bit within the applied data. These operations can be performed by a CAM array during a compare operation to block a matching entry having actively masked bits from indicating a match whenever another matching entry having a lesser number of actively masked bits is present.